1315C - Restoring Permutation - CodeForces Solution

#include <iostream>
#include<bits/stdc++.h>
using namespace std::chrono;
using namespace std;
#define ahmedIbrahim ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define yes cout<<"YES\n";
#define no cout<<"NO\n";
#define toLong(word) stoll(word)
#define toInt(word) stoi(word)
#define MB(a,b) make_pair(a,b)
#define el "\n"
typedef std::numeric_limits< double > dbl;
typedef long long ll;
typedef vector<ll> vec;

const int MOD = 1e9+7;
inline void debugMode() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}
ll powFast(ll x, ll y)
{
    x %= MOD;
    ll ans = 1;
    while(y)
    {
        if(y & 1) ans = ans * x % MOD;
        x = x * x % MOD;
        y >>= 1;
    }
    return ans;
}

double lineEqu(long long x1,long long y1,long long x2,long long y2){
    return ceil(sqrt((pow((x2-x1),2)+pow((y2-y1),2))));
}

int myGCD(int x,int y){ // __gcd(x,y)
    if(y==0)return x;
    return myGCD(min(x,y), max(x,y)% min(x,y));
}
ll LCM(ll x,ll y){//least common divisor
    return (x/__gcd(x,y))*y;
}

ll add( ll x , ll y , ll M = 1e9 + 7 ){
    return ( x%M + y%M )%M ;
}

ll sub( ll x , ll y , ll M = 1e9 + 7 ){
    return ( x%M - y%M + 2*M )%M ;
}

ll mul( ll x , ll y , ll M = 1e9 + 7 ){
    return ( x%M * y%M )%M ;
}


vector<ll>getAllDivisors(ll num){//sqrt(n)
    vector<ll>output;
    for (ll i = 1; i*i<=num; ++i) {
        if(num%i==0){
            output.push_back(i);
            if(num/i!=i)output.push_back(num/i);
        }
    }
    sort(output.begin(),output.end());
    return output;
}

vector<ll> prime_factorization( ll n ){//sqrt(n)
    vector<ll> res ;
    for (ll i = 2; i*i <= n; ++i) {
        while ( n % i == 0 ){
            res.push_back(i) ;
            n /= i ;
        }
    }
    if ( n > 1 ) res.push_back(n) ;
    return res ;
}

void print_queue(queue<ll> q)
{
    queue<ll> temp = std::move(q);
    while (!temp.empty()) {
        cout << temp.front()<<" ";
        temp.pop();
    }
    cout << '\n';
}
double calculate(int x1,int y1,int x2,int y2){
    return sqrt(pow(x2-x1,2)+pow(y2-y1,2));
}

bool sortSec(const pair<ll,ll> &a,const pair<ll,ll> &b)
{
    return (a.second < b.second);
}

int getMaxBit(ll num){
    return (int)log2(num);
}
//max size=1e7+5
vector<ll> sieve(ll size){//o(nlog(log(n)))
    vector<bool> prime(size,true);
    for (ll i = 2; i*i < size; ++i){ //{nlog(log(n))
        if(!prime[i])continue;
        for (ll j = i*i; j < size; j+=i)prime[j]= false;
    }
    vector<ll>nums;
    for (ll i = 2; i < size; ++i) {
        if(prime[i])nums.push_back(i);
    }
    return nums;
}
bool isBitOn(ll n, ll bit)
{
    if (n & (1 << (bit))) return true;
    else return false;
}
string convertToString(const vector<char>&a)
{
    string s;
    for (char i : a) s += i;
    return s;
}
template<typename T>
void printVector(const vector<T>&vec,bool space=true){
    for (ll i = 0; i < vec.size(); ++i) {
        if(i==vec.size()-1)cout<<vec[i]<<endl;
        else {cout<<vec[i]; if(space) cout<<" ";}
    }
}
bool isFactorial(ll n)
{
    for (int i = 1;; i++) {
        if (n % i == 0) n /= i;
        else break;
    }
    if (n == 1) return true;
    else return false;
}
bool isPowerOfTwo(ll n)
{
    ll num= (ll)log2(n);
    if((1ll<<num)==n)return true;
    else return false;
}
ll getFactorial(ll n){
    ll out=1;
    for (int i = 1; i <= n; ++i) {
        out*=i;
    }
    return out;
}
int popcount(ll x)//calculate numbers of ones in binary
{
    int rt=0;
    while(x!=0)
    {
        rt++;
        x-=(x&(-x));
    }
    return rt;
}
ll longest_increasing_subsequence(ll n,const vector<ll>&arr){
    vector<ll> d(n+1, 1000000000);
    for (ll i = 0; i < n; i++) {
        *lower_bound(d.begin(), d.end(), arr[i]) = arr[i];
    }
    for (ll i = 0; i <= n; i++) {
        if (d[i] == 1000000000) {
            return i;
        }
    }
}
ll FactorialMod(ll n,ll mod=1000000007){
    ll out=1;
    for (int i = 1; i <= n; ++i) {
        out*=i;
        out%=mod;
    }
    return out;
}
vector<ll>Primes;
bool isPrime(ll num){
    return any_of(Primes.begin(), Primes.end(),[num](ll y){return num==y;});
}
void deleteVector(int index,vector<ll>&arr){
    vector<ll>::iterator it;
    it = arr.begin()+index+1;
    arr.erase(it);
}
template<typename T>
bool checkSet(T x,set<T>&arr){
    if(arr.find(x)!=arr.end()) return true;
    return false;
}

ll myCeil(ll n,ll k){
    return (n%k==0)?(n/k):((n/k)+1);
}
ll getGreaterPowerOdTwo(ll n){
    ll x=2,tmp=0,pow=1;
    while (x<=n){
        if(n % x == 0)tmp=pow;
        x*=2;
        pow++;
    }
    return tmp;
}
void solve();

void deletePairVector(ll index,vector<pair<ll,ll>>&arr){
    vector<pair<ll,ll>>::iterator it;
    it = arr.begin()+index;
    arr.erase(it);
}
ll gcdExtended(ll a, ll b, ll *x, ll *y)
{
    if (a == 0)
    {
        *x = 0, *y = 1;
        return b;
    }
    ll x1, y1;
    ll gcd1 = gcdExtended(b%a, a, &x1, &y1);
    *x = y1 - (b/a) * x1;
    *y = x1;
    return gcd1;
}
ll modInverse(ll b, ll m)
{
    ll x, y;
    ll g = gcdExtended(b, m, &x, &y);
    if (g != 1)return -1;
    return (x%m + m) % m;
}


ll modDivide(ll a, ll b, ll m)
{
    a = a % m;
    int inv = modInverse(b, m);
    return (inv * a) % m;
}
ll allMul(ll n) {//summation (i^2) from 1--n
    ll a= mul(n,n+1);
    ll b= mul(2,n)+1ll;
    ll ans= mul(a,b);
    ll out=(ans* 337)%MOD;
    return out;
}
ll sum(ll n)//summation (i) * (i+1) from 1--n
{
    ll a= mul(n,n+1);
    ll b= mul(a,n+2);
    ll out=(b* 674)%MOD;
    return out;
}

void findNums(ll X, ll Y)
{
    ll A, B;
    // Case 1: X < Y ans X-Y is odd
    if (X < Y || (X-Y) % 2 !=0 ) {
        cout<<-1<<endl;
        return;
    }
        // Case 3: If both Sum and XOR are equal
    else if (X == Y) {
        A = 0;
        B = Y;
    }
        // Case 4: If above cases fails
    else {
        A = (X - Y) / 2;
        // Check if A & Y value is 0
        if ((A & Y) == 0) {
            B = (A + Y);
        }
        else {
            cout<<-1<<endl;
            return;
        }
    }
    cout << A << " " << B<<endl;
}
int main() {
    ahmedIbrahim
    ll t=1; cin>>t;
    while (t--) {
        solve();
    }
}

void solve(){
    ll n; cin>>n;
    vec arr((2*n)+1,0);
    vector<bool> hash(2*n,false);
    for(ll i = 1 ; i <= n ; i++){
        ll x; cin>>x;
        hash[x]=true;
        arr[2*i]=x;
    }
    for(ll i = 1 ; i <= 2*n ; i+=2){
        if(i==(2*n)){
            for (ll j = 1; j <= 2*n; ++j) {
                if(!hash[j]){
                    arr[i]=j;
                    hash[j]=true;
                    break;
                }
            }
            break;
        }
        for (ll j = arr[i+1]; j <= 2*n; ++j) {
            if(!hash[j]){
                arr[i]=j;
                hash[j]=true;
                break;
            }
        }
        if(!arr[i]){
            cout<<-1<<el;
            return;
        }
    }
    for(ll i = 1 ; i < arr.size() ; i+=2){
        swap(arr[i],arr[i+1]);
    }
    for(ll i = 1 ; i < arr.size() ; i++){
        cout<<arr[i]<<" ";
    }
    cout<<el;

}